package leetcode.list;

/**
 * Created by zxc on 2018/10/9.
 * 给定一个链表，删除链表中倒数第n个节点，返回链表的头节点。
 * 给出链表1->2->3->4->5->null和 n = 2.
 删除倒数第二个节点之后，这个链表将变成1->2->3->5->null.
 O(n)时间复杂度
 */
public class RemoveNthFromEnd {

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
        }
    }

    ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode first=head;
        ListNode sec=head;
        for(int i=0;i<n;i++){
            first=first.next;
        }
        if(first==null){
            head=head.next;
            return head;
        }
        while(first.next!=null){
            first=first.next;
            sec=sec.next;
        }
        sec.next=sec.next.next;
        return head;
    }

}
